﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;
using Opennav.MapGenerator.Geometry;
using System.IO;

namespace Opennav.MapGenerator.Map.MapTiles
{
    public static class MapUtils
    {
        #region Douglas-Peucker Algorithm

        /// <summary>
        /// Simplifies a polyline.
        /// </summary>
        public static Coordinate[] DouglasPeucker(Coordinate[] polyline, double tolerance)
        {
            List<Coordinate> result = new List<Coordinate>();
            result.Add(polyline.First());
            DouglasPeuckerPrepare(polyline, tolerance, result);
            result.Add(polyline.Last());
            return result.ToArray();
        }

        private static void DouglasPeuckerPrepare(Coordinate[] polyline, double tolerance, List<Coordinate> simple)
        {
            if (polyline.First().Equals(polyline.Last()))
            {
                double dmax = 0;
                int index = 0;
                for (int i = 1; i < polyline.Length - 1; i++)
                {
                    int dx = polyline[i].Longitude - polyline[0].Longitude;
                    int dy = polyline[i].Latitude - polyline[0].Latitude;
                    double d = Math.Sqrt(dx * dx + dy * dy);
                    if (d > dmax)
                    {
                        dmax = d;
                        index = i;
                    }
                }
                if (dmax >= tolerance)
                {
                    DouglasPeucker(polyline, 0, index, tolerance, simple);
                    simple.Add(polyline[index]);
                    DouglasPeucker(polyline, index, polyline.Length - 1, tolerance, simple);
                }
            }
            else
            {
                DouglasPeucker(polyline, 0, polyline.Length - 1, tolerance, simple);
            }
        }

        private static void DouglasPeucker(Coordinate[] polyline, int start, int end, double tolerance, List<Coordinate> simple)
        {
            double dmax = 0;
            int index = 0;
            for (int i = start + 1; i < end; i++)
            {
                double d = PerpendicularDistance(polyline[i], polyline[start], polyline[end]);
                if (d > dmax)
                {
                    dmax = d;
                    index = i;
                }
            }
            if (dmax >= tolerance)
            {
                DouglasPeucker(polyline, start, index, tolerance, simple);
                simple.Add(polyline[index]);
                DouglasPeucker(polyline, index, end, tolerance, simple);
            }
        }

        private static double PerpendicularDistance(Coordinate p, Coordinate A, Coordinate B)
        {
            double Ax = A.Longitude, Ay = A.Latitude, Bx = B.Longitude, By = B.Latitude, px = p.Longitude, py = p.Latitude;
            return Math.Abs(((Bx - Ax) * (Ay - py) - (By - Ay) * (Ax - px)) / Math.Sqrt((Bx - Ax) * (Bx - Ax) + (By - Ay) * (By - Ay)));
        }

        #endregion

        #region Sutherland-Hodgman Algorithm

        /// <summary>
        /// Clips a polygon to a box.
        /// </summary>
        public static Coordinate[] SutherlandHodgman(Coordinate[] polygon, Area box)
        {
            List<Coordinate> result = new List<Coordinate>(polygon);
            for (int edge = 0; edge < 4; edge++)
            {
                List<Coordinate> clipped = new List<Coordinate>();
                bool lastInside = true;
                for (int i = 0; i < result.Count; i++)
                {
                    bool inside = false;
                    switch (edge)
                    {
                        case 0: inside = result[i].Longitude <= box.MaxLongitude; break;
                        case 1: inside = result[i].Latitude <= box.MaxLatitude; break;
                        case 2: inside = result[i].Longitude >= box.MinLongitude; break;
                        case 3: inside = result[i].Latitude >= box.MinLatitude; break;
                    }
                    if (lastInside && inside)
                        clipped.Add(result[i]);
                    else if (i > 0 && (inside || lastInside))
                    {
                        double ax = result[i - 1].Longitude, bx = result[i].Longitude;
                        double ay = result[i - 1].Latitude, by = result[i].Latitude;
                        double dx = bx - ax;
                        double dy = by - ay;
                        double factor = 0.0;
                        switch (edge)
                        {
                            case 0: factor = ((double)box.MaxLongitude - ax) / dx; break;
                            case 1: factor = ((double)box.MaxLatitude - ay) / dy; break;
                            case 2: factor = ((double)box.MinLongitude - ax) / dx; break;
                            case 3: factor = ((double)box.MinLatitude - ay) / dy; break;
                        }
                        clipped.Add(new Coordinate((int)(ax + dx * factor), (int)(ay + dy * factor)));
                        if (inside)
                            clipped.Add(polygon[i]);
                    }
                    lastInside = inside;
                }
                if (!clipped.First().Equals(clipped.Last()))
                    clipped.Add(clipped.First());
                result = clipped;
            }
            return result.ToArray();
        }

        #endregion

        #region Liang-Barsky Algorithm

        /// <summary>
        /// Clips a line to a box.
        /// </summary>
        public static Coordinate[] LiangBarsky(Coordinate a, Coordinate b, Area box)
        {
            double t0 = 0;
            double t1 = 1;
            double x0 = a.Longitude;
            double x1 = b.Longitude;
            double y0 = a.Latitude;
            double y1 = b.Latitude;
            double dx = x1 - x0, dy = y1 - y0;

            double p = -dx;
            double q = -(box.MinLongitude - x0);
            double r = q / p;

            if (p == 0 && q < 0) return null;
            if (p < 0)
            {
                if (r > t1) return null;
                else if (r > t0) t0 = r;
            }
            else if (p > 0)
            {
                if (r < t0) return null;
                else if (r < t1) t1 = r;
            }

            p = dx;
            q = box.MaxLongitude - x0;
            r = q / p;

            if (p == 0 && q < 0) return null;
            if (p < 0)
            {
                if (r > t1) return null;
                else if (r > t0) t0 = r;
            }
            else if (p > 0)
            {
                if (r < t0) return null;
                else if (r < t1) t1 = r;
            }

            p = -dy;
            q = -(box.MinLatitude - y0);
            r = q / p;

            if (p == 0 && q < 0) return null;
            if (p < 0)
            {
                if (r > t1) return null;
                else if (r > t0) t0 = r;
            }
            else if (p > 0)
            {
                if (r < t0) return null;
                else if (r < t1) t1 = r;
            }

            p = dy;
            q = box.MaxLatitude - y0;
            r = q / p;

            if (p == 0 && q < 0) return null;
            if (p < 0)
            {
                if (r > t1) return null;
                else if (r > t0) t0 = r;
            }
            else if (p > 0)
            {
                if (r < t0) return null;
                else if (r < t1) t1 = r;
            }

            Coordinate[] result = new Coordinate[2];

            if (t0 == t1)
                return null;

            if (t0 == 0.0)
                result[0] = a;
            else
                result[0] = new Coordinate((int)(x0 + t0 * dx), (int)(y0 + t0 * dy));

            if (t1 == 1.0)
                result[1] = b;
            else
                result[1] = new Coordinate((int)(x0 + t1 * dx), (int)(y0 + t1 * dy));
            return result;
        }

        #endregion

        #region MapLine/Shape Bitstream

        //static int debugId = 0;

        public static byte[] Make(Coordinate[] coords, MapTile tile)
        {
            //double tolerance = Math.Pow(2.0, (double)(tile.Zoom.Shift));
            //Coordinate[] coords = MapUtils.DouglasPeucker(coordinates, tolerance);
            int prevLon = 0;
            int prevLat = 0;
            int maxDeltaLon = 0;
            int maxDeltaLat = 0;
            List<int> deltaLons = new List<int>();
            List<int> deltaLats = new List<int>();
            List<bool> signLons = new List<bool>();
            List<bool> signLats = new List<bool>();

            //FileStream debug = new FileStream(string.Format("debug{0}", debugId++), FileMode.Create, FileAccess.Write);
            //BinaryWriter debugWriter = new BinaryWriter(debug);

            for (int i = 0; i < coords.Length; i++)
            {
                //int absLon = Math.Abs(coords[i].Longitude) >> tile.Zoom.Shift;
                //int absLat = Math.Abs(coords[i].Latitude) >> tile.Zoom.Shift;
                //bool signLon = coords[i].Longitude < 0;
                //bool signLat = coords[i].Latitude < 0;
                //int lon = signLon ? -absLon : absLon;
                //int lat = signLat ? -absLat : absLat;
                int lon = coords[i].Longitude >> tile.Zoom.Shift;
                int lat = coords[i].Latitude >> tile.Zoom.Shift;
                if (i > 0)
                {
                    int deltaLon = lon - prevLon;
                    int deltaLat = lat - prevLat;
                    if (deltaLon != 0 || deltaLat != 0)
                    {
                        int absDeltaLon = Math.Abs(deltaLon);
                        int absDeltaLat = Math.Abs(deltaLat);
                        bool signDeltaLon = deltaLon < 0;
                        bool signDeltaLat = deltaLat < 0;
                        if (absDeltaLon > maxDeltaLon) maxDeltaLon = absDeltaLon;
                        if (absDeltaLat > maxDeltaLat) maxDeltaLat = absDeltaLat;

                        deltaLons.Add(absDeltaLon);
                        deltaLats.Add(absDeltaLat);
                        signLons.Add(signDeltaLon);
                        signLats.Add(signDeltaLat);
                    }
                }
                //debugWriter.Write(string.Format("{0:0.0000} {0:0.0000}\n", Coordinate.IntToFloatCoordinate(lon << tile.Zoom.Shift), Coordinate.IntToFloatCoordinate(lat << tile.Zoom.Shift)));
                prevLon = lon;
                prevLat = lat;
            }

            //debug.Close();

            int startLon = coords[0].Longitude >> tile.Zoom.Shift;
            int startLat = coords[0].Latitude >> tile.Zoom.Shift;

            int cLon = startLon, cLat = startLat;

            for (int i = 0; i < deltaLons.Count; i++)
            {
                cLon += (signLons[i] ? -deltaLons[i] : deltaLons[i]);
                cLat += (signLats[i] ? -deltaLats[i] : deltaLats[i]);
            }

            int targetLon = coords[coords.Length - 1].Longitude >> tile.Zoom.Shift;
            int targetLat = coords[coords.Length - 1].Latitude >> tile.Zoom.Shift;

            //Console.WriteLine(string.Format("From: {0} {1} To: {2} {3}", startLon, startLat, targetLon, targetLat));

            bool isFixedSignLon = true;
            bool isFixedSignLat = true;
            bool fixedSignLon = false;
            bool fixedSignLat = false;
            for (int i = 0; i < signLons.Count; i++)
            {
                if (i == 0)
                {
                    fixedSignLon = signLons[i];
                    fixedSignLat = signLats[i];
                }
                else
                {
                    if (signLons[i] != fixedSignLon) isFixedSignLon = false;
                    if (signLats[i] != fixedSignLat) isFixedSignLat = false;
                }
            }

            BitWriter writer = new BitWriter();

            int baseLon = 0;
            if (maxDeltaLon > 0) baseLon = (int)Math.Ceiling(Math.Log(maxDeltaLon + 1, 2.0));
            int baseLat = 0;
            if (maxDeltaLat > 0) baseLat = (int)Math.Ceiling(Math.Log(maxDeltaLat + 1, 2.0));
            Debug.Assert(baseLon <= 15);
            Debug.Assert(baseLat <= 15);

            writer.Write((uint)baseLon, 4);
            writer.Write((uint)baseLat, 4);

            if (isFixedSignLon)
            {
                writer.WriteBit(1);
                writer.WriteBit(fixedSignLon ? (uint)1 : (uint)0);
            }
            else
                writer.WriteBit(0);

            if (isFixedSignLat)
            {
                writer.WriteBit(1);
                writer.WriteBit(fixedSignLat ? (uint)1 : (uint)0);
            }
            else
                writer.WriteBit(0);

            for (int i = 0; i < deltaLons.Count; i++)
            {
                if (!isFixedSignLon) writer.WriteBit(signLons[i] ? (uint)1 : (uint)0);
                writer.Write((uint)deltaLons[i], baseLon);
                if (!isFixedSignLat) writer.WriteBit(signLats[i] ? (uint)1 : (uint)0);
                writer.Write((uint)deltaLats[i], baseLat);
            }

            return writer.Data;
        }

        #endregion
    }
}
